﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

namespace LeetCodeProject
{
    internal class DPClass
    {
        private static Dictionary<int, int> dict = new Dictionary<int, int>();

        #region 爬楼梯动态规划

        /*
         * 假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。
         */

        /// <summary>
        /// 递归1
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>       
        public static int Jump_1(int n)
        {
            if (n <= 2)
                return n;
            else
            {
                return Jump_1(n - 1)+Jump_1(n-2);
            }
        }

        /// <summary>
        /// 递归2
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Jump_2(int n)
        {

            if (n <= 2)
            {
                return n;
            }
            else if (dict.ContainsKey(n))
            {
                return dict[n];
            }
            else
            {
                int res = Jump_2(n - 1) + Jump_2(n - 2);
                dict.Add(n, res);
                return res;
            }
        }

        /// <summary>
        /// 动态规划
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Jump_3(int n)
        {
            int[] list = new int[n + 1];
            list[0] = 0;
            list[1] = 1;
            list[2] = 2;
            if (n <= 2)
            {
                return n;
            }
            else
            {
                for(int i = 3; i < n+1; i++)
                {
                    list[i] = list[i - 1] + list[i-2];
                }
                return list[n];
            }            
        }
        #endregion

        #region 找零钱

        /*
         * 假设您是一个收银员，有若干种面额的硬币（比如 1 元、5 元、10 元），给定一个要找零的金额 n 
         * 求最少需要多少枚硬币才能凑出这个找零金额。
         */

        /// <summary>
        ///动态规划
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int Coin(int n)
        {
            int[]dp=new int[n+1];
            foreach(int i in dp)
            {
                dp[i] = int.MaxValue;
            }
            for(int i = 1; i <= n; i++)
            {
                if (i < 5)
                {
                    dp[i] = i;
                }
                else if (i == 5)
                {
                    dp[i] = 1;
                }
                else if (i < 10)
                {
                    dp[i] = dp[i - 5] + 1;
                }
                else if (i == 10)
                {
                    dp[i] = 1;
                }
                else if(i>10)
                {
                    dp[i] = dp[i - 10] + 1;
                }
            }
            return dp[n];
        }

        /// <summary>
        /// 递归
        /// </summary>
        public static int Coin_1(int n)
        {
            if (n < 5)
            {
                return n;
            }else if(n == 5)
            {
                return 1;
            }else if (n < 10)
            {
                return Math.Min(Coin_1(n - 1) + 1, Coin_1(n-5)+1);
            }else if (n == 10)
            {
                return 1;
            }
            else
            {
                return Math.Min(Coin_1(n-10)+1, Math.Min(Coin_1(n - 1) + 1, Coin_1(n - 5) + 1));
            }
        }
        #endregion

        #region 最长上升子序列

        /*
         * Longest Increasing Subsequence，简称 LIS
         * 给定一个整数序列，求这个序列中最长的上升子序列的长度。
         * 例如，对于序列 [10, 22, 9, 33, 21, 50, 41, 60] ，其最长上升子序列为 [10, 22, 33, 50, 60] ，长度为 5 。
         */

        /*
         * 在使用动态规划解决 “最长上升子序列” 问题时，通常会使用两层循环。
         * 外层循环遍历数组中的每个元素，内层循环用于在当前元素之前寻找比其小的元素，
         * 并根据这些比较结果更新当前元素对应的最长上升子序列长度。
         * 外层循环控制整体的计算流程，内层循环用于进行具体的比较和更新操作。
         * 时间复杂度为 O(n^2) ，其中 n 是输入数组的长度。空间复杂度为 O(n) ，用于存储 dp 数组。
         */
        public static int LastLongUpQ(int[] values)
        {
            int[]dp=new int[values.Length];
            int max = 0;
            for(int i=0; i<values.Length; i++)
            {
                dp[i] = 1;
                for(int j = 0; j < i; j++)
                {
                    if (values[i] > values[j])
                    {
                        dp[i] = Math.Max(dp[i], dp[j]+1);
                    }
                }
                if (dp[i] > max) max = dp[i];
            }
            return max;
        }

        #endregion


        #region 背包问题
        public static int BagP(int bagweight, int[,]values)
        {
            int[,]dp=new int[values.GetLength(0)+1,bagweight+1];
            for(int i=0;i< dp.GetLength(0); i++)
            {
                for(int j = 0; j < dp.GetLength(1); j++)
                {
                    dp[i, j] = 0;

                }
            }

            for(int i=1 ; i<= values.GetLength(0);i++)
            {
                int w = values[i-1,0];
                int v = values[i-1,1];
                for( int j = 1; j <= bagweight; j++) {
                    if (w > j)
                    {
                        dp[i, j] = dp[i-1, j];
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j - w] + v, dp[i-1,j]);
                    }
                }
            }
            for (int i = 0; i < dp.GetLength(0); i++)
            {
                for (int j = 0; j < dp.GetLength(1); j++)
                {
                    Console.Write(dp[i,j]+"\t");
                }
                Console.WriteLine();
            }
            return dp[values.GetLength(0), bagweight];
        }
        #endregion


        #region 莱文斯坦距离-编辑距离
        /*
         * 个字串之间，由一个转成另一个所需的最少编辑操作次数。
         * 编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
         * 例如，字符串 "kitten" 与 "sitting" 的编辑距离是 3 ，通过以下操作可以将 "kitten" 转换为 "sitting" ：
         * kitten → sitten （将 'k' 替换为's' ）
         * sitten → sittin （将 'e' 替换为 'i' ）
         * sittin → sitting （在末尾插入 'g' ）
         */

        public static int Levenshtein_distance(string strfrom,string strto)
        {
            int len1=strfrom.Length;
            int len2=strto.Length;
            int[,]dp=new int[len1+1,len2+1];
            for(int i = 0; i < len1; i++)
            {
                for(int j = 0; j < len2; j++)
                {
                    if (i == 0)
                    {
                        dp[i, j] = j;
                    }else if (j == 0)
                    {
                        dp[i, j] = i;
                    }
                    else dp[i, j] = int.MaxValue;
                }
            }
            for(int i=1;i<=len1; i++)
            {
                for(int j=1;j<= len2; j++)
                {
                    if (strfrom[i - 1] == strto[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1];
                    }
                    else
                    {
                        int del = dp[i-1,j]+1;//删除
                        int insert = dp[i,j-1]+1;//插入
                        int rep = dp[i-1,j-1]+1;//替换
                        dp[i, j] = Math.Min(del, Math.Min(insert, rep)) ;
                    }
                }
            }
            return dp[len1, len2];
        }
        /*
         * 这段代码是一个使用动态规划来计算两个字符串之间的莱文斯坦距离（编辑距离）的有效实现。
         * 以下是对这段代码的逐步分析：
         * 首先，创建了一个二维数组 dp 来存储中间计算结果。通过两个嵌套的循环初始化了边界情况，即当一个字符串为空时（i = 0 或 j = 0 ），编辑距离就是另一个字符串的长度。
         * 然后，通过两层嵌套的循环计算两个字符串中每个位置的编辑距离。
         * 如果当前比较的两个字符相等，那么当前位置的编辑距离就等于前一个位置的编辑距离（不进行任何操作）。
         * 如果不相等，分别计算删除、插入和替换操作后的编辑距离，并取最小值作为当前位置的编辑距离。
         * 最终，返回 dp[len1, len2] ，即两个完整字符串的编辑距离。
         */
        #endregion

        #region 不同路径
        /*
         * 有一个 m 行 n 列的网格，一个机器人从左上角（0，0）出发，只能向右或者向下移动，
         * 到达右下角（m - 1，n - 1）有多少种不同的路径。
         */

        public static int PathCount(int m,int n)
        {
            int[,]dp=new int[m,n];            
            for(int i = 0; i < m; i++)
            {
                dp[i, 0] = 1;
            }
            for(int j=0; j<n; j++)
            {
                dp[0,j]= 1;
            }
            for(int i=1 ; i<m; i++)
            {
                for(int j=1;j<n; j++)
                {
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
                }
            }
            return dp[m-1,n-1];
        }
        #endregion

        #region 最长公共子序列

        /*
         * Longest Common Subsequence，LCS
         * 给定两个字符串，找出它们的最长公共子序列的长度。
         * 公共子序列是指在两个字符串中都出现的子序列，子序列中的字符不一定在原字符串中是连续的。
         * 例如，对于字符串 "ABCBDAB" 和 "BDCABA"，它们的最长公共子序列是 "BCBA" ，长度为 4 。
         */

        public static int LCS(string str1,string str2)
        {
            int len1 = str1.Length;
            int len2 = str2.Length;
            int[,]dp=new int[len1+1,len2+1];
            for(int i=0; i<=len1; i++)
            {
                dp[i, 0] = 0;                
            }
            for (int i = 0; i <= len2; i++)
            {
                dp[0,i] = 0;
            }
            for (int i=1 ; i<=len1; i++)
            {
                for( int j=1 ; j<=len2; j++)
                {
                    if (str1[i - 1] != str2[j - 1])
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                    }
                    else
                    {
                        dp[i, j] = dp[i-1, j - 1] + 1;
                    }
                }
            }
            return dp[len1, len2];
        }
        #endregion
    }
}
